package _11_整理题目._4_动态规划._跳跃游戏;

import org.junit.Test;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * https://www.nowcoder.com/practice/58e31b785f4b4ced9695dd4fcd60c1ce?tpId=230&tqId=2364376&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Ftab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D230
 *
 * 三、能到最后一个位置，求最大的路径和
 *
 * 给定一个非负整数数组nums，假定最开始处于下标为0的位置，
 * 数组里面的每个元素代表下一跳能够跳跃的最大长度，同时代表积分，
 * 如果可以跳到数组最后一个位置，请你求出跳跃路径中所能获得的最多的积分。
 *
 * 动态规划：
 *      定义dp子问题，递推公式，边界条件
 *      定义 dp[i]，代表到达下标 i 获得的最高分数，则 dp[n-1] 为所求。
 *      递推公式，dp[i] = nums[i] + max( dp[j] (j<i ; j+nums[j]>=i) )
 *      边界条件，dp[0] = nums[0]
 *
 */
public class _03_跳跃游戏_最大路径和 {

    // 动态规划 1
    public int jump1(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (j+nums[j] >= i) {
                    dp[i] = Math.max(dp[i], dp[j]+nums[i]);
                }
            }
        }
        System.out.println(Arrays.toString(dp));
        return dp[n-1];
    }

    // 动态规划 2
    public int jump2(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        PriorityQueue<int[]> pq = new PriorityQueue<>( (o1, o2) -> o2[0] - o1[0] );
        for (int i = 0; i < n; i++) {
            while (!pq.isEmpty()) {
                int[] arr = pq.peek();
                int dpMax = arr[0];
                int jMax = arr[1];
                if (jMax + nums[jMax] < i) {
                    pq.poll();
                } else {
                    dp[i] = nums[i] + dpMax;
                    break;
                }
            }
            pq.offer(new int[]{dp[i], i});
        }
        System.out.println(Arrays.toString(dp));
        return dp[n-1];
    }

    // 贪心算法
    public int jump4(int[] nums) {
        int n = nums.length;
        int maxScore = 0; // 最大的积分
        int rightMax = 0; // 初始化最开始可以跳跃的最远位置
        int stepEnd = rightMax; // 每一步的最后位置
        for (int i = 0; i < n; i++) {// 遍历所有可跳跃位置，除了最后一次位置
            rightMax = Math.max(rightMax, i+nums[i]);// 更新最远位置
            // 遍历到每一步的最后一个位置时，步数加一，并更新下一步的最后位置

        }
        return maxScore;
    }

    @Test
    public void test() {
        int[] nums = {2,4,2,1,0,100};
        System.out.println(jump1(nums));
        System.out.println(jump2(nums));
    }
}
